

#include "stdafx.h"

#include <malloc.h>
#include <string.h>
#include <windows.h>

#include <stdlib.h>
#include <time.h>

#include <map>
#include <vector>
#include <bitset>

using namespace std;
unsigned char* _ps_field = NULL;

int sz_ps_field = 10000000;

void _init_ps_field()
{
	_ps_field = (unsigned char*) malloc (sz_ps_field);
	memset( _ps_field, 0, sz_ps_field);

	sz_ps_field *= 7;
}

void _clean_ps_field()
{
	if(_ps_field != NULL) free(_ps_field);
}

inline void _mark_ps_field(int pos)
{
	int byte_ps = pos / 0x7;
	int bit_pos = pos - (byte_ps * 0x7);
	
	_ps_field[byte_ps] |= 1 << (bit_pos);
}

inline bool _get_sign_bit(int pos)
{
	int byte_ps = pos / 0x7;
	int bit_pos = pos - (byte_ps * 0x7);

	bool retv = _ps_field[byte_ps] & (1 << (bit_pos));

	return (retv == true); 
}

void _test_mark_ps_field()
{
	_mark_ps_field( 7 );

	if(_get_sign_bit( 23 )) printf("error\n");
	if(!_get_sign_bit( 7 )) printf("error\n");
}

inline void _store_ps_value(unsigned int key, unsigned int value)
{
	for(unsigned int j = 0; j < 32; j++ ) {		
		if( (value & (1 << j)) ) {
			unsigned int pos = (( key ^ (j + 10) * 0xFF2343 )) % sz_ps_field;
			_mark_ps_field(pos);
		} 
	}

	//mark the key in the field 
	for(unsigned int j = 0; j < 3; j++) {
		unsigned int pos = (( key ^ (j + 10) * 0xFF2343 )) % sz_ps_field;
			_mark_ps_field(pos);
	}
}

inline unsigned int _get_ps_value(unsigned int key)
{
	unsigned int v = 0;
	for(unsigned int j = 0; j < 32; j++ ) {	
		unsigned int pos = (( key ^ (j + 10) * 0xFF2343 )) % sz_ps_field;
		if(_get_sign_bit(pos)) {
			v |= 1 << j;
		} 
	}
	return v;
}

bool _check_key(unsigned int key)
{
	int km = 0;
	for(unsigned int j = 0; j < 3; j++) {
		unsigned int pos = (( key ^ (j + 10) * 0xFF2343 )) % sz_ps_field;
		if(_get_sign_bit(pos)) km++;
	}

	if(km >= 2) return true;
}

void _test_map_capacity()
{
	int TI = GetTickCount();
	map<int,int> _map;
	map<int, int>::iterator _ITR;
	for(int i = 0; i < 15000000; i++)
	{
		_map[i] = i;
	}
	int err = 0;
	for(int i = 0; i < 15000000; i++)
	{
		_ITR = _map.find( i );

		if(_ITR != _map.end())
			err++;
	}
	int TF = GetTickCount();
	printf( "time to proc %d ms num of err %d.\n", TF - TI, err );
	printf("Press any key to continue\n");
	getchar();
}


map<unsigned int, unsigned int> _mptst;
map<unsigned int, unsigned int>::iterator _ITRMP;

void _test_insert_ps(int num)
{
	int TI = GetTickCount();
	unsigned k,v;
	for(int i = 0; i < num; i++) {
		k = i;
		v = rand();
		//_mptst[i] = v;
		_store_ps_value( k, v);
	}
	int TF = GetTickCount();
	printf("time to insert keys %d ms.\n", TF - TI );
}

void _error_test()
{
	int nerr = 0;
	_ITRMP = _mptst.begin();

	for( ; _ITRMP != _mptst.end(); _ITRMP ++) {
		unsigned k, v;

		k = _ITRMP->first;
		v = _get_ps_value(k);

		if(v != _ITRMP->second) nerr++;
	}

	printf("num of error %d\n", nerr );
}

int _tmain(int argc, _TCHAR* argv[])
{
	_init_ps_field();

	unsigned int key = 34444;
	unsigned int value = 3453455;
	_store_ps_value(key, value);

	_test_insert_ps( 10000 );
	_error_test();

	if(!_check_key(34444)) printf("error\n");
	if(_check_key(34444)) { 
		printf("key was found %u\n", _get_ps_value(key));
	}

	//_test_map_capacity();

	return 0;
}

